package com.jhy.new2025.BinaryTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 后序遍历 左右根
 * 前序遍历 根左右 -》根右左 -》左右根
 */
public class postorderTraversal {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> treeNodes = new Stack<>();
        if(root == null){
            return res;
        }
        treeNodes.push(root);
        while (!treeNodes.isEmpty()) {
            TreeNode pop = treeNodes.pop();
            Integer value = pop.val;
            res.add(value);
            if(pop.left != null) treeNodes.push(pop.left);
            if(pop.right!=null) treeNodes.push(pop.right);
        }
        Collections.reverse(res);
        return res;
    }
}
